package edu.dayu.demo3;

import java.util.HashMap;
import java.util.Map;

/**
 * 给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。
 * 输入:nums = [1,1,1], k = 2
 * 输出: 2
 * 解释: 此题 [1,1] 与 [1,1] 为两种不同的情况
 * 思路：滑动窗口吗? 最开始选择一个值，然后一直加，知道> 然后窗口右移, 妈的有负数，滑动不了。。。。。
 *      2、这道题是非常经典的前缀和 类型，首先我们可以记录 0-1，0-2... 的sum和，如果要求 1-2只需要用 0-2 - 0-1即可。
 *      所以问题就转变为了 sum[j] - sum[i] =k 的 问题。
 */
public class 和为k的子数组 {
    public static void main(String[] args) {
        int[] nums = {-1,-1,1};
        System.out.println(subarraySum(nums,0));
    }

    public static int subarraySum(int[] nums, int k) {
        int res = 0;
        if(nums == null || nums.length==0){ // 空数组处理
            return res;
        }
        int len = nums.length;
        int[] sum = new int[len];
        sum[0] = nums[0];
        for(int i=1; i<len; i++){ // 预处理，得到所有前缀和值， sum[i] 表示 nums 数组中 [0， i] 元素的和
            sum[i] = sum[i-1] + nums[i];
        }
        // 最精彩的部分 —— （[j , i]元素的和 == k） 可以转化为 （sum[i] - sum[j] == k） 可以转化为 （sum[i] - k == sum[j] ）
        // 因此我们只需要找出存在几个这样的 sum[k], 使得 （sum[i] - k == sum[j]）
        // 为了统计  sum[j] 的个数，我们使用 HashMap 进行记录 ，其 key 为 sum[j] 的值，value 为值相同的 sum[j] 的个数

        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1); // 当前前缀和即等于 k ——  sum[i] - k == 0

        for(int i=0; i<nums.length; i++){
            int temp = sum[i] - k;
            res += map.getOrDefault(temp, 0); // 得到指定 sum[j] 数量
            // 存储 sum [i] 的数量，如果存在 sum[j] 就可以直接拿到。
            map.put(sum[i], map.getOrDefault(sum[i], 0) + 1); // 统计在 i 之前相同的 sum[j] 的个数
        }
        return res;

    }
}
